package practice.tree.four;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/8/21 19:55
 */
public class BinarySearchTree extends BinaryTree {

    @Override
    public void add(Integer val) {
        elementNotNull(val);
        if (root == null) {
            root = createTreeNode(val, null);
            size++;
            afterAdd(root);
        }

        TreeNode node = root;
        TreeNode parent = root;
        while (node != null) {
            parent = node;
            if (node.val > val) {
                node = node.left;
            } else if (node.val < val) {
                node = node.right;
            } else {
                node.val = val;
                return;
            }
        }

        TreeNode newNode = createTreeNode(val, parent);
        if (parent.val > val) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }
        size++;
        afterAdd(newNode);
    }

    public void add(List<Integer> datas) {
        for (Integer data : datas) {
            add(data);
        }
    }

    protected void afterAdd(TreeNode node) {

    }

    public void remove(Integer val) {
        remove(node(val));
    }

    private void remove(TreeNode node) {
        if (node == null || root == null) return;
        size--;
        if (node.hasTwoChildren()) {
            TreeNode s = successor(node);
            node.val = s.val;
            node = s;
        }
        // 1 0
        TreeNode repacement = node.left != null ? node.left : node.right;
        if (repacement != null) {
            if (node.parent == null) {
                root = repacement;
                afterRemove(node, repacement);
                return;
            }
            repacement.parent = node.parent;
            if (node.parent.left == node) {
                node.parent.left = repacement;
            } else {
                node.parent.right = repacement;
            }
            afterRemove(node, repacement);
            return;
        }

        if (node.parent == null) {
            root = null;
            afterRemove(node, null);
            return;
        }

        if (node.parent.left == node) {
            node.parent.left = null;
        } else {
            node.parent.right = null;
        }
        afterRemove(node, null);
    }

    protected void afterRemove(TreeNode node, TreeNode replacement) {

    }

    private TreeNode node(Integer val) {
        elementNotNull(val);
        TreeNode node = root;
        while (node != null) {
            if (node.val > val) {
                node = node.left;
            } else if (node.val < val) {
                node = node.right;
            } else {
                return node;
            }
        }
        return null;
    }

    // 前驱节点
    public TreeNode predecessor(TreeNode node) {
        if (node == null || root == null) return null;
        TreeNode p = node.left;
        if (p != null) {
            while (p.right != null) p = p.right;
            return p;
        }
        while (node.isLeftChild()) node = node.parent;
        return node.parent;
    }

    // 后继节点
    public TreeNode successor(TreeNode node) {
        if (node == null || root == null) return null;
        TreeNode s = node.right;
        if (s != null) {
            while (s.left != null) s = s.left;
            return s;
        }
        while (node.isRightChild()) node = node.parent;
        return node.parent;
    }

    public int height() {
        if (root == null) return 0;
        int height = 1;
        int levelSize = 1;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            levelSize--;
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            if (levelSize == 0) {
                height++;
                levelSize = queue.size();
            }
        }
        return height;
    }

    public boolean isComplete() {
        if (root == null) return false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean leaf = false;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (leaf && !node.isLeaf()) return false;
            if (node.hasTwoChildren()) {
                queue.offer(node.left);
                queue.offer(node.right);
            } else if (node.left == null && node.right == null) {
                leaf = true;
            } else if (node.left == null && node.right != null) return false;
            else {
                queue.offer(node.left);
                leaf = true;
            }
        }
        return true;
    }
}
